An intersection between two curves may be defined to be any contiguous region in which they are geometrically coincident. An intersection between a curve and itself (i.e., a self-intersection) may be defined to be any contiguous region where sections of the curve at different parameter values are geometrically coincident. Furthermore, intersections may be split into two main categories: discrete and continuous intersections. A discrete intersection lies at a single geometrical point in Cartesian space, and two points in parameter space. A continuous intersection on the other hand (also known as an overlap intersection) can occupy two distinct continuous regions in parameter space and usually a continuous region in Cartesian space also. Both discrete and continuous intersections may be classified as crossing, tangent, or endpoint-touch intersections. The finding of intersections between curves (and between a curve and itself) is an important operation in geometry management. It is used in such areas as local and global trimming, Boolean operations, and self-intersection detection, all of which are core geometry management functions. It is thus desirable that detection of intersections is accurate, reliable and economical in terms of time and memory.
A current method for finding generic intersections employed by geometry managers is essentially a rootfinding approach where the problem is expressed in terms of a distance function of which the zeroes are to be found in several evaluations. Each evaluation of the distance function itself requires a Newton-Raphson relaxation, as the problem of closest approach has also been expressed internally in terms of finding the zeroes of a suitable function. Thus, the overall relaxation to each root is a “Newton-Raphson-squared” process whereby a Newton-Raphson solve is performed at each step of an “owning” Newton-Raphson solve. Several drawbacks have been identified using the current method described above. First, there is a loss of context when rootfinding where the rootfinder only has access to a protocol interface that it uses to evaluate function values and derivatives. While this does make the rootfinder completely generic and able to attempt a solution of any 1d rootfinding problem, it makes it impossible to adapt the method to deal with specific problems. A particular issue rootfinding near cusps, where the derivatives on each curve are small: both Newton-Raphson and Brent are unreliable in this area. Second is complexity, in that the totality of routines for finding generic intersections are widely dispersed throughout the code: around 20 files are used in the core routines of the splitter, the distance function definition, the cigars, closest-approach and rootfinding. This makes understanding and debugging difficult, and has further implications when modifying the code. Third is unreliability, in that intersection-finding is poor near to offset cusps, and intersections can also fail to be found in non-cusp models. Even when intersections are found successfully, many warnings may be output as the intersector tries to converge to “ghost” roots, either on virtual extensions or otherwise. Fourth is no tangent-finding, in that the current generic intersector will not find tangent intersections. This is a fundamental limitation of the method of looking for sign changes in the distance function, as there is no sign change at a tangency. Fifth is speed, in that one Newton-Raphson loop is used within another during relaxation has implications for speed and memory usage. And lastly is asymmetry, in that the problem of intersection-finding is a-priori symmetrical: no curve is more important in any sense than the other. However, the method used to find intersections introduces asymmetry as it treats each curve differently. This can cause problems if the curve order changes: different numbers of intersections may be found, or the intersections found may be at slightly different locations. This has consequences for the calling routines-ideally any calling routine should be able to rely on the results of intersecting curve A with curve B being the same as the results of intersecting curve B with curve A.
What is needed is a new intersector that resolves the drawbacks of the above.